package leetcode.median;

import java.util.LinkedList;
import java.util.List;

import leetcode.base.TreeNode;

public class $129_SumNumbers {

    List<String> res = new LinkedList<>();

    public int sumNumbers(TreeNode root) {
        return dfs2(root, 0);
    }

    private void dfs(TreeNode root, StringBuilder sb) {
        if (root.left == null && root.right == null) {
            sb.append(root.val);
            res.add(sb.toString());
            sb.deleteCharAt(sb.length() - 1);
            return;
        }
        sb.append(root.val);
        if (root.left != null)
            dfs(root.left, sb);
        if (root.right != null)
            dfs(root.right, sb);
        sb.deleteCharAt(sb.length() - 1);
    }

    private int dfs2(TreeNode root, int prevSum) {
        if (root == null) {
            return 0;
        }
        int sum = prevSum * 10 + root.val;
        if (root.left == null && root.right == null) {
            return sum;
        } else {
            return dfs2(root.left, sum) + dfs2(root.right, sum);
        }
    }
}
